package org.example.myleet.p403;

import java.util.HashSet;

/**
 * 102 ms
 * 动态规划 + 二分查找
 */
public class Solution {

    private static final int[] RANGE = new int[]{-1, 0, 1};

    public boolean canCross(int[] stones) {
        int len = stones.length;
        HashSet<Integer>[] dpK = new HashSet[len];
        HashSet<Integer> dp0 = new HashSet<>();
        dp0.add(0);
        dpK[0] = dp0;
        for (int i = 0; i < len - 1; ++i) {
            if (i > 0 && stones[i] - stones[i - 1] > i) {
                return false;
            }
            HashSet<Integer> possibleK = dpK[i];
            if (possibleK != null && !possibleK.isEmpty()) {
                for (Integer k : possibleK) {
                    int nextStone, nextI, nextK;
                    for (int r : RANGE) {
                        nextK = k + r;
                        if (nextK > 0) {
                            nextStone = stones[i] + nextK;
                            nextI = findNextI(stones, i, nextStone);
                            if (nextI > 0 && nextI <= len - 1) {
                                if (dpK[nextI] == null) {
                                    dpK[nextI] = new HashSet<>();
                                }
                                dpK[nextI].add(nextK);
                            }
                        }
                    }
                }
            }
        }
        HashSet<Integer> possibleK = dpK[len - 1];
        return possibleK != null && !possibleK.isEmpty();
    }

    private int findNextI(int[] stones, int start, int target) {
        int r = stones.length - 1, l = start;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (stones[mid] > target) {
                r = mid;
            } else if (stones[mid] < target) {
                l = mid;
            } else {
                return mid;
            }
        }
        if (stones[l] == target) {
            return l;
        }
        if (stones[r] == target) {
            return r;
        }
        return -1;
    }
}
